class Solution 
{
public:
    int numDecodings(string s) 
    {
        int n =s.size();
        vector<int> dp(n);
        if(s[0]=='0') dp[0]=0;
        else dp[0]=1;
        if(n==1) return dp[0];
        int num=std::stoi(s.substr(0,2));
        //此时有一种
        if(s[0]!='0'&&s[1]!='0') dp[1]=1;
        if(num>=10&&num<=26) dp[1]++;
        for(int i=2;i<n;i++)
        {
            int cur=s[i]-'0';
            int prev=s[i-1]-'0';
            //单独方法不满足说明此时dp[i] =0;需要看两种解码可能吗？
            if(cur>=1&&cur<=9) dp[i]=dp[i-1];
            else dp[i]=0;
            //可以的话加上
            //不可以的话就是dp[i]
            int sum=prev*10+cur;
            if(sum>=10&&sum<=26) dp[i]+=dp[i-2];
            
        }
        return dp[n-1];

    }
};


class Solution 
{
public:
    int numDecodings(string s) 
    {
        int n =s.size();
        vector<int> dp(n+1);
        //dp(2)可能会用到dp(0)比如两种情况都成立dp(2)==dp(0)+dp(1)
        dp[0]=1;
        dp[1]=s[0]=='0'?0:1;
        //新dp表的下表是下一个位置
        for(int i=2;i<=n;i++)
        {
            int cur=s[i-1]-'0';
            int prev=s[i-2]-'0';
            //单独方法不满足说明此时dp[i] =0;需要看两种解码可能吗？
            if(cur>=1&&cur<=9) dp[i]=dp[i-1];
            else dp[i]=0;
            //可以的话加上
            //不可以的话就是dp[i]
            int sum=prev*10+cur;
            if(sum>=10&&sum<=26) dp[i]+=dp[i-2];
            
        }
        return dp[n];

    }
};